package Sort;


import java.util.Arrays;
import java.util.Collections;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: homechen
 * Date: 2024-03-09
 * Time: 14:23
 */
public class quickSort {

    private static int QuickSortSignal(int[] array, int left, int right) {
        int key = left;// 选取最左边位置作为 key，注意不是 0,递归右边的时候，下标，不是 0
        int tmp = array[key];
        while (left < right) {
            while (left < right && array[right] >= tmp) { // 避免死循环问题
                right--;
            }
            while (left < right && array[left] <= tmp) {
                left++;
            }
            // 找到两个对应的位置 进行左右交换
            Swap.swap(array, left, right);
        }
        // 循环结束条件，两个位置相撞  直接交换key位置和相撞位置
        Swap.swap(array, left, key);

        return left;
    }

    private static void QuickSort(int[] array, int left, int right) {
        if (left >= right) {
            return; // 此时只有一个元素时，mid - 1 肯定小于 left
        }
        int mid = QuickSortSignal(array, left, right); // 返回相撞位置
        QuickSort(array, left, mid - 1); // 递归左边
        QuickSort(array, mid + 1, right); // 递归右边
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 4, 2, 5, 6, 2, 35, 3, 3, 55, 1, 3, 14, 53};
        QuickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

}
